import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/*
 * @lc app=leetcode.cn id=60 lang=java
 *
 * [60] 第k个排列
 *
 * https://leetcode-cn.com/problems/permutation-sequence/description/
 *
 * algorithms
 * Medium (47.22%)
 * Likes:    136
 * Dislikes: 0
 * Total Accepted:    15.9K
 * Total Submissions: 33.7K
 * Testcase Example:  '3\n3'
 *
 * 给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
 *
 * 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
 *
 *
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 *
 *
 * 给定 n 和 k，返回第 k 个排列。
 *
 * 说明：
 *
 *
 * 给定 n 的范围是 [1, 9]。
 * 给定 k 的范围是[1,  n!]。
 *
 *
 * 示例 1:
 *
 * 输入: n = 3, k = 3
 * 输出: "213"
 *
 *
 * 示例 2:
 *
 * 输入: n = 4, k = 9
 * 输出: "2314"
 *
 *
 */

// @lc code=start
class Solution {
    int[] dp = null;
    List<String> list = null;
    public String getPermutation(int n, int k) {
        dp = new int[n+1];
        dp[0] = 1;
        list = new ArrayList<>();
        for(int i=1; i <= n; i++) {
            dp[i] = i * dp[i-1];
            list.add(String.valueOf(i));
        }
        return fun(n, k);
    }

    String fun(int n, int k) {
        if(n == 1) {
            return list.get(0);
        }
        int index = (k-1) / dp[n-1];
        String s = list.get(index);
        list.remove(index);
        return s + fun(n-1, k - index * dp[n-1]);
    }
}
// @lc code=end

